The present invention relates to a search method for values or keys or memory addresses stored in an address table, and to an address compare circuit for carrying out the search method.
The recovery of stored data by means of a search word relating to these data is an important objective of information processing. A system providing the possibility of such content-related access is called associative or content addressble memory (CAM).
Conventional (semiconductor) memories are accessed on the basis of an address statement, that is to say by specifying the position of the desired data item in memory. Hitherto, only a few associative memories (CAM's) have been available as components on the market. Their memory capacity is quite small so that their use is restricted to special fields.
Larger associative memories are built up from conventional memory elements and an additional retrieval unit which implements the associative access function. The retrieval unit searches the memory contents for the predetermined key (search word). In this context, many different search strategies are conceivable which differ in implementation effort and access time. Specialized hardware or an appropriately programmed computer can be used as the retrieval unit.
The most widely used search strategies for retrieval units according to the key transformation method are the so-called variance or hashing methods. The hashing methods offer very good efficiency with low implementation expenditure. The usual hashing methods have the characteristic that the average search effort is small but that the search time exceeds the average by a multiple in the worst case. This effect makes the use of hashing methods in real-time systems considerably more difficult since the strict maintenance of time conditions must be ensured in such systems.
However, there is a class of hashing functions which do not have the above-mentioned disadvantages, which are the so-called perfect hashing functions which guarantee a uniform, very low access effort for all cases, see Communications of the ACM, Vol. 24, Dec. 1981, pages 829-833. Perfect hashing function guarantee that a key will be retrieved with a single probing, that is to say with a single access.
If W is a set of elements from interval X=[0 . . . n], n being the largest element of internal X, a perfect key transformation function or hashing function h will unambiguously map the set W in a map interval I=[0 . . . m] of integers, m being the largest element of interval I. Using h as element-to-address transformation, the elements w of the set W are stored in an address table T with a firmly predetermined number of elements m. The following applies to all elements w from the set W: EQU T(h(w))=w.
That is to say, an element w is contained in the set W exactly when the value w is found at the position or at the table index h(w) of the address table T. Searching for an element w in the address table T thus requires a calculation of the function h and a compare operation.
Calculating the hashing function h(w) is carried out by means of hashing function tables. With an unresolved, direct arrangement of the function h(w) in a memory as a hashing function table, a memory having a size of EQU C.sub.d =n.times.[log.sub.2 m]
bits is needed with binary coding. [log.sub.2 m] denotes the smallest integer greater than or equal to log.sub.2 m. With today's technology, this direct arrangement requires very elaborate memories for n &gt;10.sup.5. In addition, storage utilization is low since in typical applications of associative memories the assumption is that n&gt;&gt;m.
The present invention relates to search methods as described in Communications of the ACM, Vol. 24 (1981), pages 829-833. In this document, two algorithms for calculating perfect hashing functions are specified which have been primarily designed for implementation in software on a high-performance computer. These functions are only conditionally suitable for implementation in hardware since their calculation requires, among other things, multiplying and dividing operations.
The implementation of discrete functions (hashing functions belong to this class) in hardware can be carried out simply and efficiently by means of function tables, see IEEE Transactions on Computers, Vol. 27 (1980), pages 931-934. These tables can be stored in large-scale integrated, inexpensive semiconductor memories.
Such search methods for memory addresses and address compare circuits can be used, for example, in a text editor where a line with a certain identifier is required, that is to say where not only the presence of an element but also its position is of interest. In distributed control and monitoring or process control systems operating in accordance with the principal of source addressing, associative receiver circuits are also needed, see, for example, Swiss Patent Specification 632,365. In this document, a data exchange method between several subscribers or partners and their processors is specified in which for useful messages to be transmitted, apart from these messages, a sender address but no receiver address is transmitted. The sender address and the data type are used by all active subscribers to decide whether the useful message is of interest to them. For this purpose, they have to compare this sender address with at least one address stored in a table.
In future high speed transmission systems, associative receiver circuits of correspondingly high performance must be used. With transmission rates of 10 MHz-100 MHz, associative memories of the order of magnitude of 100.times.24 bits to 5000.times.24 bits with an access time in the range of 1 .mu.s to 10 .mu.s are needed in the receivers.